package Hot100.Medium.Backtracking;

import java.util.*;

public class LC17 {
    public static void main(String[] args) {

    }

    /**
     * 回溯法
     * @param digits
     * @return
     */
    public List<String> letterCombinations1(String digits){
        List<String> res = new ArrayList<>();
        if(digits.equals("1")){
            return res;
        }
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jklm");
        map.put('6', "nopq");
        map.put('7', "rst");
        map.put('8', "uvw");
        map.put('9', "xyz");
        backtracking(0, map, res, digits, new StringBuffer());
        return res;
    }

    public static void backtracking(int n, Map<Character, String> map, List<String> res, String digits, StringBuffer combination){
        if(n == digits.length()){
            res.add(combination.toString());
        }else{
            char digit = digits.charAt(n);
            String letters = map.get(digit);
            int lettersCount = letters.length();
            for(int i = 0; i < lettersCount; i++){
                combination.append(letters.charAt(i));
                backtracking(n + 1, map, res, digits, combination);
                combination.deleteCharAt(n);
            }
        }

    }

    /**
     * 非回溯法
     * @param digits
     * @return
     */
    public List<String> letterCombinations2(String digits){
        List<String> res = new ArrayList<>();
        if(digits.length() == 0)
            return res;

        Map<Character, List<String>> map = new HashMap<>();
        map.put('2', Arrays.asList("a","b","c"));
        map.put('3', Arrays.asList("d","e","f"));
        map.put('4', Arrays.asList("g","h","i"));
        map.put('5', Arrays.asList("j","k","l"));
        map.put('6', Arrays.asList("m","n","o"));
        map.put('7', Arrays.asList("p","q","r","s"));
        map.put('8', Arrays.asList("t","u","v"));
        map.put('9', Arrays.asList("w","x","y","z"));
        res = map.get(digits.charAt(0));

        if(digits.length() == 1) return res;
        int i = 1;
        while(i < digits.length()){
            List<String> temp = new ArrayList<>();
            for(String s1 : res){
                List<String> str = map.get(digits.charAt(i));
                for(String s2 : str){
                    temp.add(s1 + s2);
                }
            }
            res = temp;
            i++;
        }
        return res;
    }
}
